1. Technical Field
This invention relates to information processors, and more particularly to a Fine-Grained Microstructure Processor for associating, or correlating, one set of two-dimensional data with another.
2. Discussion
Assignment and correlation problems are among the most difficult to solve using conventional information processors. Assignment problems include those in which a number of entities are to be selected from among many and assigned to other entities in such a way as to force the entire assignment over all entities to be optimal in some sense. In correlation problems entities in one set of data are correlated with entities in another set of data. These problems are difficult to solve because they are not generally solvable with a single solution but, instead there may be a range of solutions of which the best solution is sought. Moreover, these problems frequently involve a combinatorial explosion or exponential blowup in the number of possible answers.
Examples of assignment and correlation problems include, among others, resource allocation, object association, two-dimensional position-only track initiation, deghosting for angle-only targets detected by multiple sensors, pattern matching of two-dimensional feature vectors, template matching and two-dimensional filtering.
Previous approaches in this area have emphasized solutions in software on both general purpose and special purpose (vector, array, systolic, etc.) computers. The disadvantage of a software approach is that it requires explicit algorithm nd software development and massive computational power. In addition, software solutions are not feasible for application to real-time or near real-time problems. For example, for two-dimensional position-only track initiation problems, estimates for conventional approaches indicate that for a scenario of N objects detected by a sensor, the best conventional algorithms would require on the order of N squared operations. For example, including minimum estimates for memory access and other overhead, with N equal to 100,000 about 10.sup.11 operations per scan would be required. For a ten second scan this equates to 10 billion operations per second, well beyond the realm of conventional solutions.
Another approach to solving these problems is a technique called simulated annealing. See S. Kirkpatrick, Glatt, and Vecchi: "Optimization By Simulated Annealing", 220 Science, p. 671-680 (1983). However, while algorithms using this approach have been developed, to the applicant's knowledge, actual working architecture have not been implemented. Also, in the image processing domain, systolic and single-planar correlation processors may exist, but are usually limited to in-plane interconnect structures with fixed templates or two-dimensional filtering structures.
Thus, it would be desirable to provide an information processor that can solve assignment and correlation problems of realistic sizes in real-time. It would further be desirable to provide a processor capable of solving these problems without requiring extensive algorithm and software development. Also, it would be desirable to provide such a processor, which can be easily implemented in hardware, while requiring a minimum of size, weight, and power.